今天來看序列 DP。

序列 DP 是跟字串相關的動態規劃，基本題的就是求最長共同子序列 (LCS/Longest common string) 。和背包問題不同，序列 DP 通常把兩個元素（字串）放在不同維度，一個元素作為對照組，然後把另一個元素切成多個部分（字元），依次遍歷並記錄資訊。這算是動態規劃的經典題之一，念演算法都會唸到。

522. Longest Uncommon Subsequence II 這題其實有點挑錯，看解題文選的，但寫完發現可以不用 DP 欸QAQ（比較好的寫法是 2 pointer）

還是解釋一下：這題會給多個字串，要找出最長的 substring，且這個 substring 不是其他字串的 substring。要解題需要下面的技巧：

1. 怎麼確定 a 是不是 b 的 substring
   • 用雙指針去找：a 和 b 兩個字串從頭開始比對，一直對到 b 字串的末尾，看能不能抓出 a
   • 複雜度是 O(max(len(a), len(b)))
2. substring 的組合有很多種，怎麼找複雜度才不會超標
   • 假設 c 是 a 的 substring，如果 c 不是任何人的 substring，那 a 也不可能是任何人的 substring
   • 從上面概念出發，這題化簡後其實不用考慮每個元素的子字串，每個元素都直接拿來搜就好了

最核心的邏輯是上面標粗體的地方，如果沒有理解這點，整題就會難以下手，感覺之後的字串或 LCS 應該蠻有可能繼續用到這個概念的。

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def is_subseq(s: str, t: str) -> bool:
            pt_s = pt_t = 0
            while pt_s < len(s) and pt_t < len(t):
                if s[pt_s] == t[pt_t]:
                    pt_s += 1
                pt_t += 1
            return pt_s == len(s)
        
        strs.sort(key=len, reverse=True)

        for ind, s in enumerate(strs):                
            check = True
            for j, t in enumerate(strs):
                if ind != j and is_subseq(s, t):
                    check = False
                    break

            if check:
                return len(s)
        
        return -1

• 序列 DP
  • 522. Longest Uncommon Subsequence II

Total Count: 17